package com.yubest;

/**
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 *
 *
 *
 * 示例 :
 * 给定二叉树
 *
 *           1
 *          / \
 *         2   3
 *        / \
 *       4   5
 * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
 *
 *
 *
 * 注意：两结点之间的路径长度是以它们之间边的数目表示。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/10 16:49
 */
public class P0543 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));

        System.out.println(new Solution543().diameterOfBinaryTree(root));
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution543 {

    private int max = 0;

    /**
     * 思路：其实就是计算每个节点左子树 最大深度 + 右子树最大深度 之和，取最大值即是结果
     * @param root
     * @return
     */
    public int diameterOfBinaryTree(TreeNode root) {
        if (null == root || root.left == null && root.right == null) {
            return 0;
        }

        int left = null != root.left ? depth(root.left) + 1 : 0;
        int right = null != root.right ? depth(root.right) + 1 : 0;
        max = Math.max(max, left + right);

        diameterOfBinaryTree(root.left);
        diameterOfBinaryTree(root.right);

        return max;
    }

    private int depth(TreeNode node) {
        if (null == node) {
            return 0;
        }
        int left = null != node.left ? depth(node.left) + 1 : 0;
        int right = null != node.right ? depth(node.right) + 1 : 0;
        return Math.max(left, right);
    }
}
